//现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为 正整数。请返回每段竹子长度的 最大乘积 是多少。 
//
// 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 
//
// 
//
// 示例 1： 
//
// 
//输入：bamboo_len = 12
//输出：81
// 
//
// 
//
// 提示： 
//
// 
// 2 <= bamboo_len <= 1000 
// 
//
// 注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/ 
//
// 
//
// Related Topics 数学 动态规划 👍 270 👎 0


package LeetCode.editor.cn;


import java.math.BigInteger;
import java.util.Arrays;

/**
 * @author ldltd
 * @date 2025-04-28 15:19:47
 * @description LCR 132.砍竹子 II
 
 */
 
public class JianShengZiIiLcof {
    public static void main(String[] args) {
    //测试代码
    JianShengZiIiLcof fun = new JianShengZiIiLcof();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        int mod= (int) (1e9+7);
        /*
        * 不能用动态规划，因为会导致中间的值变化
        *
        *
        * */
    public int cuttingBamboo(int bamboo_len) {
        BigInteger[] dp = new BigInteger[bamboo_len + 1];
        Arrays.fill(dp, BigInteger.valueOf(1));
        // dp[1] = BigInteger.valueOf(1);
        for(int i = 3; i < bamboo_len + 1; i++){
            for(int j = 1; j < i; j++){
                dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j))).max(dp[i - j].multiply(BigInteger.valueOf(j)));
            }
        }
        return dp[bamboo_len].mod(BigInteger.valueOf(1000000007)).intValue();
    }

    public int cuttingBamboo1(int bamboo_len) {
        if(bamboo_len<3) return 1;
        if(bamboo_len==3) return 2;
        long res=1;
        while (bamboo_len>4){
            res=(res*3)%mod;
            bamboo_len-=3;
        }
        res=(res*bamboo_len)%mod;
        return (int) res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
